package com.lab303.powerproject.util;//请用utf8进行编译：-encoding utf8
import java.util.*;
import java.util.stream.Collectors;//该类自java-8引入，如果编译环境不支持java-8或以上环境，请删掉本行及main方法重新编译


/**
 *   使用约定：
 *   使用构造方法new一个对象之后，用addEdge方法来添加边，所以边添加完成后，用getResult方法计算。
 *   用getResult方法计算后，不可以再添加边，如果需要请再new一个对象重新一一加边再次计算；
 *   但可以多次调用getResult方法查看结果，多次调用getResult方法返回值均相同。
 *   查看某个具体节点的分配策略，使用query方法。
*/

public class MinCost {

    private static Comparator<int[]> cmp = new Comparator<int[]>() {
        @Override
        public int compare(int[] p1, int[] p2) {
            return p1[0] - p2[0];
        }
    };

    public static class Edge {
        int cap;
        final int to, cost, rev;
        final boolean positive;

        Edge(int to, int cap, int cost, int rev, boolean positive) {
            this.to = to;
            this.cap = cap;
            this.cost = cost;
            this.rev = rev;
            this.positive = positive;
        }
    }

    private static final int INF = 0x3f3f3f3f;

    private final int n;
    private int result;
    private final List<List<Edge>> G;

    //用来检查节点是否合法的辅助方法
    private boolean validNode(int node) {
        return 0 <= node && node < n;
    }

    /**
     * @return 图的节点个数
     */
    public int nodeNum() {
        return n;
    }

    /**
     * 构造方法
     * @exception IllegalArgumentException 如果节点的个数小于两个
     * @param n 图的节点个数
     */
    public MinCost(int n) {
        if (n < 2) {
            throw new IllegalArgumentException("节点的个数应大于等于两个");
        }

        this.n = n;
        result = -INF;
        G = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            G.add(new ArrayList<>());
        }
    }

    /**
     * 为这个图添加一条边，请在用getResult方法计算前添加，用getResult方法计算后不允许再加边，
     * 如果需要在另一个图上计算，请new另外一个对象重新加边进行计算。
     * @param from 该边的出发节点
     * @param to 该边的进入节点
     * @param cap 该边的最大容量
     * @param cost 该边单位流的费用
     * @exception IllegalStateException 如果在调用getResult方法计算之后调用此方法
     * @exception IllegalArgumentException from和to的值不在[0, n)的范围内，或cap和cost的值为负
     */
    public void addEdge(int from, int to, int cap, int cost) {
        if (result != -INF) {
            throw new IllegalStateException("进行运算之后不能重新加边，请用一个新的对象重新加边计算");
        }
        if (!validNode(from) || !validNode(to)) {
            throw new IllegalArgumentException("from和to的值应在[0, n)之间");
        }
        if (cap < 0 || cost < 0) {
            throw new IllegalArgumentException("cap和cost的值应为非负值");
        }
        // 加一条容量为0的边没有意义，所以直接返回
        if (cap == 0) {
            return;
        }

        G.get(from).add(new Edge(to, cap, cost, G.get(to).size(), true));
        G.get(to).add(new Edge(from, 0, -cost, G.get(from).size() - 1, false));
    }

    /**
     * 添加所有的边后，调用此方法来计算最小费用流，可多次调用，但调用之后请勿再加边
     * @param source 源点
     * @param dest 汇点
     * @param flow 要发送的流的大小
     * @return 从source发送flow大小的流到dest的最小费用，如果无法发送这么大的流返回-1
     * @exception IllegalArgumentException source和dest不在[0, n)之间，或flow为负
     */
    public int getResult(int source, int dest, int flow) {
        if (result == -INF) {
            result = solve(source, dest, flow);
        }
        return result;
    }

    //使用Dijkstra算法的、在残存网络上寻找增广路径的最小费用流算法
    private int solve(int source, int dest, int flow) {
        if (!validNode(source) || !validNode(dest)) {
            throw new IllegalArgumentException("source和dest的值应在[0, n)之间");
        }
        if (flow < 0) {
            throw new IllegalArgumentException("flow的值应为非负值");
        }

        PriorityQueue<int[]> que = new PriorityQueue<>(cmp);
        int[] dist = new int[n], h = new int[n], prevv = new int[n], preve = new int[n];
        int ans = 0;
        while (flow > 0) {
            //用Dijkstra算法在残存网络上寻找一条费用最小的增光路经
            Arrays.fill(dist, INF);
            dist[source] = 0;
            for (que.add(new int[] { 0, source }); que.size() > 0;) {
                int[] p = que.poll();
                int d = p[0], v = p[1];
                if (d > dist[v]) {
                    continue;
                }
                for (int i = 0, size = G.get(v).size(); i < size; i++) {
                    Edge e = G.get(v).get(i);
                    if (e.cap > 0 && dist[e.to] > dist[v] + h[v] - h[e.to] + e.cost) {
                        dist[e.to] = dist[v] + h[v] - h[e.to] + e.cost;
                        que.add(new int[] { dist[e.to], e.to });
                        prevv[e.to] = v;
                        preve[e.to] = i;
                    }
                }
            }
            //如果无法到达目标节点，返回-1表示无解
            if (dist[dest] >= INF) {
                return -1;
            }
            for (int v = 0; v < n; v++) {
                h[v] += dist[v];
            }
            int d = flow;
            for (int v = dest; v != source; v = prevv[v]) {
                d = Math.min(d, G.get(prevv[v]).get(preve[v]).cap);
            }
            flow -= d;
            ans += d * h[dest];
            for (int v = dest; v != source; v = prevv[v]) {
                Edge e = G.get(prevv[v]).get(preve[v]);
                e.cap -= d;
                G.get(v).get(e.rev).cap += d;
            }
        }
        return ans;
    }

    /**
     * 在getResult方法调用后，用此方法进行某个节点分配策略的查询
     * @param node 要查询的节点
     * @return 分配的策略，对于List中每个int[]，下标0存储发出流的目标节点，下标1存储发出的流的大小
     * @exception IllegalStateException 在调用getResult方法进行计算之前调用本方法
     */
    public List<int[]> query(int node) {
        if (result == -INF) {
            throw new IllegalStateException("必须先执行getResult方法进行计算再调用本方法进行查询");
        }

        List<int[]> ans = new ArrayList<>();
        for (Edge e : G.get(node)) {
            Edge revEdge = G.get(e.to).get(e.rev);
            if (e.positive && revEdge.cap > 0) {
                ans.add(new int[] { e.to, revEdge.cap });
            }
        }
        return ans;
    }


    /**
     *  main方法用来测试，测试用例以这种格式给出：
     *  边的个数m 节点个数n 流的大小f 源的编号s 汇的编号t
     *  之后有m行，每行以如下格式给出：
     *  边的出发点 边的进入点 边的最大容量 边的单位流费用
    */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt(), f = sc.nextInt(), source = sc.nextInt(), dest = sc.nextInt();
        MinCost s = new MinCost(n);
        for (int i = 0; i < m; i++) {
            s.addEdge(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
        }
        System.out.println(s.getResult(source, dest, f));
        System.out.println(s.query(0).stream().map(Arrays::toString).collect(Collectors.joining(", ")));
        sc.close();
    }
}